/* 直接插入排序 */
#include "linklist.h"
using namespace std;
#define maxsize 50

// 插入排序 -- 针对数组
void InsertSort(int R[], int n)
{
  int i, j, temp;
  
  // 假设前i-1个数有序，插入第i个元素
  for (i = 2; i <= n; ++i)
  {
    // 暂存第i个元素
    R[0] = R[i];
    
    // 找到插入的位置
    for (j = i - 1; R[0] < R[j]; --j)
      R[j + 1] = R[j];
    
    // 插入
    R[j + 1] = R[0];
  }
} 

// 插入排序 -- 针对链表
void linksort(LNode *&L)
{
  // 有序链表 -- 初始时只含一个元素
  LNode *p = L->next;
  LNode *r = p->next;
  p->next = NULL;
  p = r;
  
  // 遍历链表
  while (p != NULL)
  {
    r = p->next;
    LNode *pre = L;
    
    // 找到结点应存放的位置
    while (pre->next != NULL && pre->next->data < p->data)
      pre = pre->next;
    
    // 插入
    p->next = pre->next;
    pre->next = p;
    p = r;
  }
}

int main()
{
  // 创建数组 -- 首元素为标识符-1
  int R[] = {-1, 8, 3, 6, 15, 2};
  
  // 插入排序
  InsertSort(R, 5);
  
  // 打印
  for (int i = 1; i < 6; i++)
    {
      cout << R[i] << ' ';
    }
  
  // 创建链表
  LNode *head = create_linklist();

  // 插入排序
  linksort(head);

  // 打印
  LNode *p = head->next;
  while (p != NULL)
    {
      cout << p->data << " ";
      p = p->next;
    }
  return 0;
}
